1. Field of Invention
This invention relates generally to single dimensional search engines which could be used in electronic routers and switches.
2. Discussion of Prior Art
One of the most important applications for this invention is to perform address lookups in routers. A router is an electronic device that has several input and output ports. It receives data packets with destination addresses on each of these ports. The lookup function involves looking up these destination addresses in a table called a lookup table to determine which output port this particular data packet should be sent to, so that it gets to it's destination most efficiently. The router then sends the packet out of the output port determined by this lookup.
One method of doing this is to build a list of all the possible destinations and the best port to send a packet out of to reach each destination. Then each destination address can be searched in this table and the best outgoing port can be determined. However, in large networks like the internet the number of such destinations is so large that such a table becomes too large to be implemented in each routers. Another consideration is the maintenance of this table. Now each time a new destination is added to the network each router in the network has to be informed of this. This is very cumbersome for large networks.
Hence, to solve this problem, a prefix based lookup scheme is used to carry out routing in modern internet routers. The idea here is that the network is arranged in a hierarchical fashion and the addresses are allocated accordingly, somewhat similar to a postal address. For example take an imaginary postal address like 123, Some Street, Someville, Somestate, US. The zip code has been dropped to make the postal example more analogous. Thus, a letter with this address posted from anywhere in the world would first be sent to US. Next, the US postal system will direct the letter to Somestate, from where it will go to the city Someville and so on and so forth. Thus, this system eliminates the requirement for every post office in the world to have knowledge of where 123, Some Street is and how to deliver a letter to that address. Similarly prefixes allow the aggregation of entire sub-networks under one entry in the lookup table.
However, there are special cases that need to be taken care of. Again falling back on the postal system analogy, from some places in Canada it is more efficient to send a letter to Alaska directly there rather than sending it first to the mainland US postal system. Thus, these Canadian postal offices would have a letter routing rule book that has two entries: send letters addressed to US to the mainland US postal system, send letter addressed to Alaska, US to the Alaska postal system. Here clearly the second rule has higher precedence over the first one. This can be expressed as longest prefix matching. Thus, one should use the rule with the longest or most specific prefix for routing decisions. Similarly, in routers the longer prefix has a higher priority than a shorter prefix. This is the basic concept behind CIDR (Classless Inter-Domain Routing) which is used in routers.
Even though this concept cuts down on the number of entries that need to be maintained in the routing table, nevertheless the number of entries in the routing tables of routers in the backbone of the internet are large at around 100,000 today. To provide for adequate margin for growth during the lifetime of these routers, currently routers are shipped with the ability to support one million entries. Today these address are 32 bit long (under a scheme called IPv4) but as the stock of available address are depleted, 128 bit long address (IPv6) are coming into use.
Another factor that is making this task difficult is that the speed of the links connecting these routers is growing with rapid advances in technology. The state of the art optical fiber links today can run at 10 Gbps (called OC-192). Considering that minimum sized (40 bytes) data packet are sent over links of this capacity a lookup speed of slightly over 30 million lookups per second is required. Systems currently in development will support link speeds of 40 Gbps (OC-768) requiring a lookup speed of over 120 million lookups per second. This lookup speed is required for each link to a router. A router may have several links connected to it. Thus, overall the problem is to search for the longest prefix match for each address among a million prefixes at the speed of several hundred lookups per second. Using just prior art this is a daunting problem. The parameters of interest are power consumption, number of chips required to store and search the table and the chip area of these chips, latency of search, and the rate at which the search can be performed.
An example of a lookup table used for forwarding is shown in FIG. 1. Each entry in this table is 32 bits wide. The first column contain the prefix with the prefix length after the ‘/’. Each 32 bit address is grouped into four decimal numbers each representing 8 bits. The four decimal numbers are separated by a decimal point. For example the 32 bit long address 1010 1011 0011 0110 0010 0000 0001 0101 is 171.54.32.21 in this format.
Using these conventions, the entry, 171.54.32.0124, refers to the range of addresses from 171.54.32.0 to 171.54.32.255. Hence, the first 24 bits are defined while the last 8 bits are “don't care” bits. Another representation for the prefixes would be 171.54.32.X, where the X stands for “don't care”. The outgoing port is in the next column. An incoming address can match multiple entries. In this case the entry with the longest prefix is chosen as the best match if a CIDR algorithm is desired. For example the word 171.54.32.123 matches two entries from the table in FIG. 1, namely 171.54.0.0/16 and 171.54.32.0124. However since 171.54.32.0124 is a longer prefix than 171.54.0.0/16, the best match is 171.54.32.0124. Another method of establishing priority would be to actually specify the priority for each entry.
An alternate way to represent this table is shown in FIG. 2. Here each prefix is represented as a range along a number line (shown at the bottom of the figure). Since we are dealing with 32 bit prefix entries in this example, this number line extends from 0.0.0.0 to 255.255.255.255. Each prefix is a contiguous range on this number line. The prefixes from the table in FIG. 1 are shown on this number line. Note that the longer prefixes represent shorter ranges on this number line. If a longest prefix match is desired, then the first range that matches the address to be looked up going from top to bottom in FIG. 2 is the best match.
There are two general approaches to solving this problem. The first is to use a general CAM (Content Addressable Memory) to store and search the entire lookup table. Each CAM cells contains two memory elements to store three states (1, 0, X or don't care) and comparison circuitry to compare the destination IP address to the stored entry. This approach results in large silicon area as well as large power consumption as every entry is searched.
The second approach is to store the lookup table as some data structure in conventional memory. For example see U.S. Pat. No. 6,011,795. This data structure is designed to allow efficient lookup using a particular algorithm. A specially designed integrated circuit is used to perform the lookup on this memory. While the power in this scheme can be low, it suffers from several drawbacks. Any data structure involves a lot of wastage due to either empty entries or pointers used to navigate the structure. The factor of real prefix data to memory used is 3-4 at best and can be as bad as 64. Secondly to run this lookup at a high speed, each level of this data structure has to be pipelined. This puts a large I/O requirement on the system. Which is difficult if not impossible to meet as the number of lookups required exceed 100 Million lookups per second. Hence current techniques are expensive and have unmanageable amount of worst-case power and I/O requirements. Another disadvantage is that the latency of these solutions can be large and also the worst-case latency may be much larger than the average case latency. This large and possibly uncertain search latency requires larger and more complex buffering of the data packets.